Space-time constraints

$$ \def\F{\mathbb F} $$

Goal. Simulate a form of (random access) memory using bivariate polynomials $P\in\F[X,Y]$.

Intuitively, we lay out the memory with time on the $X$ axis and space (addresses) on the $Y$ axis.


Stack

Start with a simple stack where $P(𝜔_n^i, 𝜔_m^j)$ is the value of stack location $j$ at time $i$.

The initial polynomial is the zero polynomial on our basis $𝜔^j$

$$ P(0, Y) = Y^m - 1 $$

Note. It looks like we can handle the memory sparsely, both in the polyonmial form and in the merkle trees.

$$ L_{m,j}(Y) = \frac{𝜔_m^j}{m} \frac{Y^m - 1}{Y-𝜔_m^j} $$

Push & Pop

Constraint. (Push). Rotate all elements to the right, add an element $x$. Has the following constraints:

$$ \begin{aligned} P(X, 𝜔_m^{m-1}) &= 0 \\ P(𝜔_n ⋅ X, Y) &= P(X, 𝜔_m ⋅ Y) + x ⋅ L_0(Y) \end{aligned} $$

Constraint. (Pop). Operate the push constraint in reverse.

Random access

Constraint. (Compare and swap). Replace the value at $j$ from $a$ to $b$.

$$ \begin{aligned} P(X, 𝜔_m^j) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ L_j(Y) \end{aligned} $$

The problem here is that we need to encode the $j$ somehow, either in a precomputed polynomial or as a column. Since all usage of $j$ will be in the form $𝜔_m^j$ we will use that instead. the final constraint will look like:

$$ \begin{aligned} P(X, Q(X)) &= a \\ P(𝜔_n ⋅ X, Y) &= P(X, Y) + (b - a) ⋅ \frac{Q(X)}{m} \frac{Y^m - 1}{Y-Q(X)} \end{aligned} $$

To do. What if $Q(X)$ is not of the form $𝜔_m^j$?

The first constraint has a degree bound of $(\deg P)⋅(\deg Q) = n^2 m$. So far we have only handle constant constraint bounds. How do we LDE test this efficiently?

We could add a temporary value? $t = Q(X), P(X, t) = a$?

In addition, to force $Q(X)$ to be a root of unity, we can add a constraint

$$ Q(X)^m = 1 $$

which has degree bound $m\deg Q = nm$. Again, how do we LDE-test this efficiently?


Polynomial composition

Both approaches above hit the problem that we need to low-degree-test an expression of the form $P(Q(X))$. The straightforward approach has degree bound $(\deg P)(\deg Q)$ which is quadratic. This will kill prover performance and more than double proof size.

Goal. Find a way to LDE test polynomial compositions efficiently.

To do. Specify goal more concretely.

https://en.wikipedia.org/wiki/Polynomial_decomposition

https://www.math.mcgill.ca/rickards/PDFs/amer.math.monthly.118.04.358-rickards.pdf

https://www.cs.cornell.edu/~kozen/Papers/poly.pdf

Chebyshev polynomials have the nesting property $T_n(T_m(X)) = T_{mn}(X)$.

https://dspace.mit.edu/bitstream/handle/1721.1/71792/Kedlaya-2011-FAST%20POLYNOMIAL%20FACT.pdf?sequence=1&isAllowed=y https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf Evaluates $f(g(x)) \mod h(x)$ in less then $\mathcal O(n^2)$ time using FFTs. => Read. http://users.cms.caltech.edu/~umans/papers/U07.pdf

https://www.cse.iitk.ac.in/users/nitin/courses/CS681-2016-17-II/pdfs/slides-dwivedi.pdf

https://citeseer.ist.psu.edu/viewdoc/download;jsessionid=611B98690C1028968AED2736F9E1E77C?doi=10.1.1.51.3154&rep=rep1&type=pdf

https://arxiv.org/pdf/0807.3578.pdf


Aside: https://en.wikipedia.org/wiki/Bruun's_FFT_algorithm

Remco Bloemen
Math & Engineering
https://2π.com